package cn.cxq.learning.tree;

/**
 * 线索化二叉树
 */
public class ThreadedBinaryTree {

    private ThreadedNode root;

    //前驱节点
    private ThreadedNode pre = null;

    public void setRoot(ThreadedNode root) {
        this.root = root;
    }


    public void inorderThreadNodes() {
        inorderThreadNodes(root);
    }

    /**
     * 中序线索化二叉树
     *
     * @param node
     */
    private void inorderThreadNodes(ThreadedNode node) {

        if (node == null) return;

        inorderThreadNodes(node.getLeft());

        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }

        //处理完一个节点后让前驱节点指向当前节点
        pre = node;

        inorderThreadNodes(node.getRight());

    }

    public void preorderThreadedNodes(){
        this.preorderThreadedNodes(root);
    }

    /**
     * 前序线索化二叉树
     * @param node
     */
    private void preorderThreadedNodes(ThreadedNode node){

        if (node == null) return;

        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }

        //处理完一个节点后让前驱节点指向当前节点
        pre = node;

        if (node.getLeft() != null && node.getLeftType()==0) preorderThreadedNodes(node.getLeft());
        if (node.getRight() != null && node.getRightType()==0) preorderThreadedNodes(node.getRight());
    }

    public void postorderThreadedNodes(){
        this.postorderThreadedNodes(root);
    }

    /**
     * 后序线索化二叉树
     * @param node
     */
    private void postorderThreadedNodes(ThreadedNode node){

        if (node == null) return;

        postorderThreadedNodes(node.getLeft());
        postorderThreadedNodes(node.getRight());

        if (node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }

        if (pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }

        pre=node;

    }

    /**
     * 中序遍历线索化二叉树，这样比较方便，你用什么顺序线索化就用什么顺序遍历
     */
    public void inorderThreadedList() {

        ThreadedNode node = root;

        while (node != null) {
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }

            System.out.println(node);

            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }

    }

    public void preorderThreadedList() {

        ThreadedNode node = root;
        while (node != null) {
            while (node.getLeft() != null && node.getLeftType()==0) {
                System.out.println(node);
                node = node.getLeft();
            }
            System.out.println(node);
            if (node.getLeftType()==1) node = node.getRight();
            while (node != null && node.getRightType()==1) {
                System.out.println(node);
                node = node.getRight();
            }
        }

    }

    /**
     * 递归方式
     */
    public void postorderThreadedList(){
        postorderThreadedList(root);
    }

    public void postorderThreadedList(ThreadedNode node){
        if (node.getLeftType()==0){
            postorderThreadedList(node.getLeft());
        }
        if (node.getRightType()==0){
            postorderThreadedList(node.getRight());
        }
        System.out.println(node);
    }

    public void add(ThreadedNode node) {
        if (this.root == null) this.root = node;
        else {
            this.root.add(node);
        }
    }
}

class ThreadedNode {
    private int no;
    private String msg;
    private ThreadedNode left;
    private ThreadedNode right;

    //认定这两个类型：如果为0的话说明指向的是子树，1的话leftType是前驱节点，rightType是后驱节点。
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public ThreadedNode(int no, String msg) {
        this.no = no;
        this.msg = msg;
        this.leftType = 0;
        this.rightType = 0;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", msg='" + msg + '\'' +
                '}';
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getMsg() {
        return msg;
    }

    public void setMsg(String msg) {
        this.msg = msg;
    }

    public ThreadedNode getLeft() {
        return left;
    }

    public void setLeft(ThreadedNode left) {
        this.left = left;
    }

    public ThreadedNode getRight() {
        return right;
    }

    public void setRight(ThreadedNode right) {
        this.right = right;
    }

    public void add(ThreadedNode node) {
        if (this.no > node.no) {
            if (this.left != null) this.left.add(node);
            else {
                this.left = node;
                return;
            }
        } else {
            if (this.right != null) this.right.add(node);
            else {
                this.right = node;
                return;
            }
        }
    }
}